package codingforgreat.class39;


// 来自腾讯
// 给定一个长度为n的数组arr，求有多少个子数组满足 :
// 子数组两端的值，是这个子数组的最小值和次小值，最小值和次小值谁在最左和最右无所谓
// n<=100000（10^5） n*logn  O(N)
public class Class02_ValidSequence {
        public static int nums(int[] arr){
            int N = arr.length;
            int[] stack = new int[N];
            int[] times = new int[N];
            int size = 0;
            int ans = 0;
            for(int i = 0;i < N;i++){
                while (size != 0 && stack[size-1] > arr[i]){
                    size--;
                    ans += times[size] + Cn2(times[size]);
                }
                if(size != 0 && stack[size-1] == arr[i]){
                    times[size - 1]++;
                }else {
                    stack[size] = arr[i];
                    times[size] = 1;
                    size++;
                }
            }
            while (size != 0){
                ans += Cn2(times[--size]);
            }
            for (int i = arr.length - 1; i >= 0; i--) {
                while (size != 0 && stack[size - 1] > arr[i]) {
                    ans += times[--size];
                }
                if (size != 0 && stack[size - 1] == arr[i]) {
                    times[size - 1]++;
                } else {
                    stack[size] = arr[i];
                    times[size++] = 1;
                }
            }
            return ans;
        }
        public  static int Cn2(int n){
            return n*(n-1)/2;
        }
    // 暴力方法
    public static int test(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int ans = 0;
        for (int s = 0; s < arr.length; s++) {
            for (int e = s + 1; e < arr.length; e++) {
                int max = Math.max(arr[s], arr[e]);
                boolean valid = true;
                for (int i = s + 1; i < e; i++) {
                    if (arr[i] < max) {
                        valid = false;
                        break;
                    }
                }
                ans += valid ? 1 : 0;
            }
        }
        return ans;
    }

    // 为了测试
    public static int[] randomArray(int n, int v) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (int) (Math.random() * v);
        }
        return arr;
    }

    // 为了测试
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 为了测试
    public static void main(String[] args) {
        int n = 30;
        int v = 30;
        int testTime = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int m = (int) (Math.random() * n);
            int[] arr = randomArray(m, v);
            int ans1 = nums(arr);
            int ans2 = test(arr);
            if (ans1 != ans2) {
                System.out.println("出错了!");
                printArray(arr);
                System.out.println(ans1);
                System.out.println(ans2);
            }
        }
        System.out.println("测试结束");
    }

}
